\documentclass[a4paper,11pt]{report}
 
 \usepackage[utf8]{inputenc}
 \usepackage{amssymb,amsmath,amsfonts}
\usepackage{graphicx}
 %\pagestyle{headings} %les includes
 
 
\newlength{\larg}
\setlength{\larg}{14.5cm} %on defini un type de taille
 
 
 
 
 \title{ % la page de garde
    {\rule{\larg}{1mm}}\vspace{7mm}
	\begin{center}
	  \Huge {\bf {Rapport}} \\ Algorithme \\ Complexité \\ Calculabilité \\
	\end{center}
    }
\author{\begin{tabular}{p{13.7cm}}
Maurin Benjamin, Giner steve , Henri
\end{tabular}\\
\hline }
\date{}
 
 \renewcommand{\contentsname}{Table des matières : } % changer le titre de la table des matières

 
 %%%% Redefini le style des titres de chapitre %%%%
\makeatletter
\def\@makechapterhead#1{%
  \vspace*{30\p@}%
  {\parindent \z@ \raggedright \normalfont
    \interlinepenalty\@M
    \ifnum \c@secnumdepth >\m@ne
        \Huge\bfseries \thechapter\quad
    \fi
    \Huge \bfseries #1\par\nobreak
    \vskip 40\p@
  }}
 
 
 % \begin{itemize}
	 % \item bla bla 1
	%  \item bla bla 2
	%  \end{itemize}
 
 

 \begin{document}


\maketitle % la page de garde

  \tableofcontents % la table des matieres 

    \chapter{Partie théorique}
 
    \section{Algorithme}
    \subsection{Exercice 1}
blabla
 \subsection{Exercice 2}
      
      \subsubsection{1)}
	  Si on supprime un arc (ij) tel que f(i,j) = 0 , alors on perd un flot de 0. On ne peut pas perdre moins que 0, donc (ij) est un least vital arc.
	 \subsubsection{2)}
	 Appelons f* un flot maximum. \\
	 Montrons : \\
	 (ij) est un Least vital arc $\longrightarrow$ f(i,j) est la valeur minimum de f* : \\
	 Supposons $\exists$ a1 un Least vital arc tel que a1 $\neq$ $\min$(f*). Alors $\exists$ a2 un arc tel que f*(a2)$<$f*(a1).
	 Donc si on supprime a2, f* perd f*(a2), alors que f* perd f*(a1) si on supprime a1. Comme f*(a2)$<$f*(a1), a1 n'est pas un least vital arc. Impossible (hypothèse), donc l'implication est vraie. \\
	 Montrons : \\
	 f(i,j) est la valeur minimum de f* $\longrightarrow$ (ij) est un Least vital arc : \\
	 $\forall$arc a tel que a $=$ $\min$(f*), si on supprime a, f*(a) est supprimé de f*. Comme a est un least vital arc, $\nexists$ a2 tel que f*(a2)$<$f*(a), 
	 donc $\nexists$ d'arc qui enleve plus de flot que a lorsqu'il est supprimé.
	 Donc a est un least vital arc. 
       \subsubsection{3)}
       LVA $=$ least vital arc. \\
       Soit C1 une coupe min. On sait que les arc de C1 sont saturé dans f*.
       Donc les arcs entrant ou sortant des extremités des arcs de C1 ont forcement un flot dans f* inferieur ou égal à l'arc duquel il rentre ou sort de C1.
       Or un f*(LVA) $=$ $\min$(f*), donc un LVA $\notin$ C1 puisque un de ses arcs sortant ou entrant a une valeure inferieure. \\
       
       
  \subsection{Exercice 3}
  blabla
 \subsection{Exercice 4}
 blabla
\section{Complexité}
 \subsection{Exercice 5}
 blabla
  \subsection{Exercice 6}
  blabla
\section{Calculabilité}

 \subsection{Exercice 7}
  \subsubsection{1)}
  $\forall$ (x,y) $\in \mathbb{N} \times \mathbb{N}$, on tri (x$+$y) par ordre lexicographique. Ainsi, tous les couples d'entiers sont énumérés.
  on a alors couple(x,y) = $\frac{(x+y)(x+y+1)}{2}$+y .
  \subsubsection{2)}
  Soit z$\in\mathbb{Z}$ \\
  Codage : \\ si z$\geq$0 f1(z)$=$2z$=$x sinon f1(z)$=$2z-1$=$x \\
  Decodage : \\ si z impair f2(z) $= \frac{-(z+1)}{2} =$ y sinon f2(z) $= \frac{z}{2} =$ y
  \subsubsection{3)}
  Triplet : \\ h(x,y,z)$=$couple(x,couple(y,z)) \\
  k-uplets : \\ h(x1,x2,...,xk)=couple(x1,couple(x2,couple(x3, ... couple(xk-1,xk) ))
  \subsubsection{4)}
  Supposons l'intervalle [0,1] dénombrale : \\
  x1 $=$ 0, $x_{1}^{1}$  $x_{2}^{1}$  $x_{3}^{1}$ ... $x_{n}^{1}$ \\
  x2 $=$ 0, $x_{1}^{2}$  $x_{2}^{2}$  $x_{3}^{2}$ ... $x_{n}^{2}$ \\
  ... \\
  xp $=$ 0, $x_{1}^{p}$  $x_{2}^{p}$  $x_{3}^{p}$ ... $x_{n}^{p}$ \\
  \\ Soit vi $=$ $a_{i}^{i}$ + 1 \\
  Alors 0,v1v2v3 ... est dans la liste, et on a donc $a_{m}^{m}$ $=$ $a_{m}^{m}$ + 1 : Absurde. \\
  Donc l'intervalle [0,1] n'est pas dénombrale.
  
  \subsection{Exercice 8}
 \subsubsection{1)}
  On s'intéresse aux fonctions définies sur l'ensemble  des entiers naturels.
  On construit les fonctions récursives primitives de proche en proche en partant des trois fonctions de base :
  \begin{itemize}
	  \item La fonction identiquement nulle
	  \item La fonction Successeur Succ(t) $=$ t + 1
	  \item Les projections (x1,x2,...,xk) $\longrightarrow$ xi
  \end{itemize} 

Et en itérant la construction suivante : \\ 
	 \hspace{0.5cm} La composition de fonctions : si f1,f2,...,fk  sont récursives primitives sur $\mathbb{N}$ et si h est récursive primitive sur $\mathbb{N}$, toutes déjà définies,
	alors la fonction  \hspace{0.5cm}  g $=$ h(f1,f2,...,fk) est une nouvelle fonction récursive primitive.
\subsubsection{2)}
Un ensemble est recursif primitif si sa fonction caractéristique est recursive primitive.
\subsubsection{3)}
\begin{tabbing}
   \hspace{0.5cm} \= \\
\>(a) Somme(0,x) $=$ x \\
\>Somme(Succ(x),y) $=$ Succ(Somme(x,y))\\ \\
\>(b) Produit(0,y) $=$ 0 \\
\>Produit(Succ(x),y)= Somme (y,Produit(x,y)) \\ \\
\>(c) exp(0,y) $=$ 0 \\
\> exp(Succ(x),y) $=$ Produit(y,exp(x,y)) \\ \\
\>(d) MoinsUn(0) $=$ 0\\
\>  MoinsUn(Succ(x))=x \\ \\
\>(e)Soustraction(x,0) $=$ x\\
\> Soustraction(0,y) $=$ 0 \\
\> Soustraction(x,y) $=$ Soustraction(MoinsUn(x),MoinsUn(y)) \\ \\
\>(f) sg(0) $=$ 0\\
\> sg(x) $=$ 1 \\ \\
\>(g) Soit p la fonction caractéristique de x$>$y \\
\> p(x,y) $=$ sg(Soustraction(x,y)) \\ \\
\> Soit p' la fonction caractéristique de x$\geq$y \\
\> p'(x,0) $=$ 1  p'(0,y) $=$ 0 p'(0,0) $=$ 1 \\
\> p'(x,y) $=$ p'(MoinsUn(x),MoinsUn(y)) \\ \\
\>(h) Soit $f_{A}$ la fonction caractéristique de A \\
\> h(x1,x2,...,xn) $=$ Somme(Produit($f_{A}$(x1,x2,...,xn),f(x1,x2,...,xn)),\\ \> Produit(Soustraction(1,$f_{A}$(x1,x2,...,xn)),g(x1,x2,...,xn)) \\
\end{tabbing}

 \chapter{Partie Pratique}

 \section{Le langage C++}

Nous avons choisi ce langage de programmation pour différentes raisons.\\ Tout d'abord, c'est un langage compilé. Il est bien plus rapide qu'un langage interprété ou semi-interprété comme le Java.\\
Ensuite, le C++ nous permet d'utiliser des librairies et donc des raccourcis de programmation nous permettant de nous focaliser sur les exercices du TP et non sur la complexité d'algorithme plus classique comme ceux de tri par exemple.\\
Pour finir, c'est un langage que nous avons tous étudié à l'université et nous l'avons choisi pour ne pas être contraint par l'apprentissage du langage.


 \section{Les structures de données}

\vspace{9cm}
	\includegraphics[width=0.10\textwidth]{structure_graphe.jpg}

Le graphe tout comme le graphe d’écart ou de couche est représenté par un par un vecteur de vecteur de vecteur d’entier ( $vector$$<$$vector$$<$$vector$$<$$int$$>$ $>$ $>$ $G$ ).\\
Les sommets sont représentés par des entier allant de 0 à $n-1$, 0 étant la source et $n-1$ le puit.\\
Le premier vector est de taille $n$ (nombre de sommet du graphe). En l’indice $i$, on a le vector d’arêtes du sommet $i$. Ce vector étant lui-même un vector d’entier contenant le sommet d’arrivée de l’arête, son flot et sa capacité. Par exemple, si on veut obtenir le flot  d’une arêtes partant du sommet 2 (si elle existe), on fait $G[2][0][1]$.\\

Nous allons dans cette partie expliquer pourquoi nous avons fait le choix de cette structure et des différents objets associés.

 \subsection{Pourquoi la classe $<$vector$>$ ?}
Tout d’abord, un vector est une liste indexé. En effet, il permet d’avoir une taille variable et un accès direct à une donnée d’index $i$. On peut donc l’utiliser comme un tableau classique tout en pouvant ajouter des éléments en temps constant comme dans une liste.\\

Un autre avantage du vector, à la différence d’une matrice par exemple, est qu’il permet de n’avoir que les données nécessaires dans et donc lors d’un parcours des arêtes d’un sommet, faire un parcours de $m$ et non de $n$.\\

Le dernier avantage de cette classe est qu’elle fait partie de la librairie STL. Elle contient donc différentes fonctions, entre autres le tri ($sort()$), déjà développées et fortement optimisées par des gourous de l’informatique. Ceci nous permettant de nous concentrer sur les algorithmes du TP.\\

Le seul défaut du vector dans notre situation est la suppression d’un élément autre que le dernier pour la suppression d’arêtes. En effet, la suppression d’un élément en fin de vector se fait en temps constant par une simple réduction de la taille du vector et un changement de pointeur alors qu’à un autre endroit du vector ceci est en $O$$($$taille$ $du$ $vector$$)$. Mais nous avons réduit ce problème à quelques actions basiques : étant donné que qu’il n’y a pas d’ordre dans notre vector d’arêtes ($G[i]$), nous avons pu échanger le dernier élément du vector avec l’élément que nous voulions supprimer et supprimer le dernier élément du vector ($O(m)\rightarrow O(2)$).\\

 \subsection{Une matrice d’indice}
\vspace{5cm}
	\includegraphics[width=0.10\textwidth]{matrice.png}

Le défaut de cette structure était l'impossibilité d’atteindre en temps constant les données d’une arête. Par exemple, pour obtenir les données de l’arête $2\rightarrow 5$, on devait parcourir tout le vector de l’indice 2 ( $G[2]$ ) ce qui nous donnait un parcours en $O(m)$ et, de plus, on n’avait aucun moyen en temps constant de savoir si l’arête existait.\\
Pour pallier à ce problème nous avons décidé d’utiliser une matrice n * n contenant aux indice i,j l’indice dans le vector G[i] de l’arête $i\rightarrow j$ et une valeur par défaut pour signifier que l’arête n’existe pas (-1). Ce tableau est modifié à chaque ajout et suppression, ce qui ne coûte donc qu’une affectation de plus, chose négligeable comparé au gain occasionné sur l’accès à une arête ($O(m)\rightarrow O(1)$). 

 \section{Les algorithmes}

Les tests ont été effectué sur une machine personnelle avec un core 2 duo cadencé à 2,2 GHz et 4 Go de RAM sous Windows 7. Nous avons pris 4 nombres différents de sommets (50,500,1000,2000). Les arêtes sont ajoutées de manière aléatoire avec 2 probabilités différentes: 
\
begin{\begin{itemize}
	\item{faible densité : 50% de chances d'avoir une arêtes entre 2 sommets}
	\item{forte densité : 80% de chances d'avoir une arêtes entre 2 sommets}
\end{itemize}
Les arêtes ont une capacité comprise entre 1 et 10 (en raison de risque de temps d'exécution beaucoup trop long sur Edmond-Karp ou Ford Fulkerson). 
Chaque sommet a forcément au moins un arête entrante et une arête sortante sauf pour la source et le puit qui ont respectivement que des arêtes sortantes et que des entrantes.//
Les résultats des tests sont des moyennes de plusieurs tests.

\subsection{Edmond Karp}

\vspace{6cm}
	\includegraphics[width=0.10\textwidth]{edmondkarp.png}

Comme on peut le voir sur le graphique, le nombre d'arete du graphe a un fort impact sur le temps d'execution lorsque l'on commence a avoir un nombre de sommet élevé. Le temps d'execution est presque doublé. On peut donc en conclure que c'est un algorithme peu efficace lorsque les chemins de la source au puit sont nombreux.



\subsection{Dinic}

\vspace{6cm}
	\includegraphics[width=0.10\textwidth]{dinic.png}

On remarquera que cet algorithme est beaucoup plus rapide que le précédent (environ 2 fois plus). L'augmentation du temps de calcul en fonction du nombre de sommet est plus lente mais lorsque le graphe a une forte densité on double tout même le temps d'execution par rapport au calcul avec une faible densité. Cet algorithme traite donc mieux la multiplication des chemins qu'Edmond Karp.

\subsection{Ford-Fulkerson}
 
\vspace{6cm}
	\includegraphics[width=0.10\textwidth]{ford.png}

Cet algorithme est assez similaire à Edmond Karp dans sa manière de fonctionner, il souffre donc des mêmes défauts. Il est un peu plus rapide qu'Edmond Karp car il ne passe pas par la graphe d'écart mais reste bien moins rapide que Dinic surtout lorsque l'on augmente le nombre d'arêtes et de sommets. Nos résultats ne sont peut être pas très pertinent car la recherche des prédécesseurs se fait en $O(n)$ et non en $O(m)$ (trouver si un sommet donné est prédécesseur se fait en $O(1)$ grâce à la matrice d'indices)  comme celle des successeurs à cause de notre structure de données utilisée. Pour l'améliorer il aurait fallu créer un vecteur de prédécesseurs associés mais en contrepartie on aurait eu d'autres manipulations bien plus coûteuse comme la création, la modification et les mise à jours du graphe. 

\subsection{Capacity Scaling}

\vspace{6cm}
	\includegraphics[width=0.10\textwidth]{capacity.png}

Cette méthode est assez proche de Edmond Karp à la différence que l'on travail sur moins d'arêtes en même temps. En augmentant les capacités max possiblent sur les arêtes, on peut remarquer que cet algorithme résiste mieux que Ford Fulkerson et Edmond Karp.

\subsection{Synthèse}

Pour conclure, on peut dire que l'algorithme qui résiste le mieux à l'augmentation du nombre de sommet et d'arêtes est Dinic. En effet, la récupération d'un ensemble de plus courts chemins permet de considérablement améliorer la complexité du calcul de flot maximum. Les 3 autres algorithme ont des résultats assez similaires, mais il faudrait faire de plus grosses batteries de tests pour pouvoir observer les différences de complexité.



\end{document}